﻿// 1723. 完成所有工作的最短时间.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
/*
https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs/

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。

示例 1：
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

示例 2：
输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。


提示：
1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 107
*/


//方法1
//class Solution {
//public:
//    bool dfs(int limit, const vector<int>& jobs, int idx, vector<int>& worker, int len) {
//        if (idx >= jobs.size()) {
//            //能在每个不超过limit的情况下 放完 返回true
//            return true;
//        }
//       
//        for (int i = 0; i < len; i++) {
//            if (worker[i] == 0) {
//                worker[i] = jobs[idx];
//                if (true == dfs(limit, jobs, idx + 1, worker, len)) {
//                    return true;
//                }
//                worker[i] = 0;
//                break;
//            }
//            else {
//                if (worker[i] + jobs[idx] <= limit) {
//                    worker[i] += jobs[idx];
//                    if (true == dfs(limit, jobs, idx + 1, worker, len)) {
//                        return true;
//                    }
//                    worker[i] -= jobs[idx];
//                }
//            }
//        }
//
//        return false;
//    }
//
//    bool check(int x, const vector<int>& jobs, int k) {
//        vector<int> worker(15, 0);
//        bool ret = dfs(x, jobs,0, worker, k);
//
//        return ret;
//    }
//
//    int minimumTimeRequired(vector<int>& jobs, int k) {
//        sort(jobs.begin(), jobs.end(),greater<int>());
//        int l = *max_element(jobs.begin(), jobs.end()); int r = accumulate(jobs.begin(), jobs.end(),0);
//        while (l < r) {
//            int mid = (l + r ) >> 1; 
//            if (check(mid, jobs,k)) {
//                r = mid;
//            }
//            else {
//                l = mid+1;
//            }
//        }
//        cout << "l= " << l << endl;
//        return l;
//    }
//};

//class Solution {
//public:
//    int ans = 2000000000;
//    void dfs(const vector<int>& jobs, int idx, vector<int>& worker, int len) {
//        if (idx >= jobs.size()) {
//            ans = min(ans, *max_element(worker.begin(), worker.end() ));
//            return;
//        }
//        if (*max_element(worker.begin(), worker.end()) >= ans) return;
//
//        for (int i = 0; i < len; i++) {
//            if (worker[i] == 0) {
//                worker[i] += jobs[idx];
//                dfs(jobs,idx+1,worker,len);
//                worker[i] = 0; break;
//            }
//            else {
//                if (worker[i] + jobs[idx] <= ans) {
//                    worker[i] += jobs[idx];
//                    dfs(jobs, idx + 1, worker, len);
//                    worker[i] -= jobs[idx];
//                }
//            }
//        }
//
//        return;
//    }
//
//    int minimumTimeRequired(vector<int>& jobs, int k) {
//        sort(jobs.begin(), jobs.end(), greater<int>());
//        vector<int> worker(k, 0);
//        dfs(jobs,0, worker, k);
//
//        cout << ans << endl;
//
//        return ans;
//    }
//};

//dp[i][j] 表示 前i个 状态为j 的最大工作量
class Solution {
public:
    int sum[1 << 12];
    void init(const vector<int>& jobs, int k) {
        memset(sum, 0, sizeof sum);

        for (int i = 0; i < (1 << jobs.size()); i++) {
            for (int j = 0; j <  jobs.size(); j++) {
                if ((i >> j) & 1) {
                    sum[i] += jobs[j];
                }
            }
        }
    }

    int minimumTimeRequired(vector<int>& jobs, int k) {
        init(jobs,k);
        int dp[15][1 << 12];
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;

        for (int i = 1; i <= k; i++) {
            for (int state = 0; state < (1 << jobs.size()); state++) {
                for (int s = state; s; s = ((s - 1) & state) ) {
                    dp[i][state] = min(dp[i][state], max(dp[i - 1][state ^ s] , sum[s]));
                }
            }
        }

        //cout << dp[k][(1 << jobs.size() )- 1] << endl;

        return dp[k][(1 << jobs.size()) - 1];
    }
};


int main()
{
    Solution  s;
    vector<int> v{ 1,2,4,7,8 };
    s.minimumTimeRequired(v,2);
}

